In the previous sections we have talked about the determinism in tiling systems. To see the origin of this definitions, we must extract the implicit non-determinism of tiling systems. Therefore, we will take a look at an automaton accepting the same class of languages than tiling systems. Some definitions will look similar and make clear how this determinism is achieved. 

At first, we need some definitions about how such an automaton can move over a picture. Furthermore, we are going to customize some earlier definitions to match the requirements for tiling automaton. These definitions are from \cite{anselmo2009computational}. 

\begin{definition}
	A partial function $f: \mathbb{N}^4 \rightarrow \mathbb{N}^2$ is called \emph{next-position function}, if any defined quadruple $(i, j, m, n)$ is only using positions $(i, j) \in P(m, n)$.
\end{definition}

With $P(m, n)$ we already denoted the set of positions in picture $p$. To track the positions that are already visited, we use a sequence of visited positions. Let $f$ be a next-position function. The sequence of $k$ visited positions starting from $(i_0, j_0)$ is denoted by $V_{f, k}(m, n) = (v_1(m, n), v_2(m, n), \dots, v_k(m, n))$ where 
\begin{compactitem}
	\item $v_1(m, n) = (i_0, j_0)$ and
	\item $v_h(m, n) = f(i, j, m, n)$ with $(i, j) = v_{h - 1}(m, n)$ for $h = 2, \dots, k$. 
\end{compactitem}

Let $p$ be a picture of size $(m, n)$ and let $(i, j)$, where $1 \leq i \leq m$, $1 \leq j \leq n$, be a position in the picture $p$ which is not placed at the top or left border. The positions $(i, j - 1)$, $(i - 1, j)$ and $(i - 1, j - 1)$ are called the top-left contiguous positions of $(i, j)$. This can be similarly defined for top-right, bottom-left and bottom-right contiguous positions. We will also use the abbreviations $tl$, $tr$, $bl$ and $br$. 

\begin{definition}
	A next-position function $\mathfrak{s}$ is called a \emph{scanning strategy}, if the corresponding sequence of visited positions $V(m, n) = V_{\mathfrak{s}, k}(m, n) = (v_1(m, n), \dots, v_k(m, n))$ at step $k = (m + 2) \cdot (n + 2)$ satisfies the following conditions: 
	
	\begin{compactitem}
		\item $v_1(m, n)$ is the top-left, top-right, bottom-left or bottom-right corner,
		\item $V(n, m)$ is a permutation of $P(n, m)$ and 
		\item for any $k = 2, \dots, (m + 2) \cdot (n + 2)$ either the top-left, top-right, bottom-left or bottom right contiguous positions of $v_k(m, n)$ are in $V_{\mathfrak{s}, k}(m, n)$ or are borders. 
	\end{compactitem}
\end{definition}

In other words, a scanning strategy is a next-position function, which starts at a corner of the picture, visits every position of the picture exactly one time and for each visited position the contiguous positions in one direction are already visited or are at the border of the picture. Therefore, every corner fulfills the last condition because of the three border pixels surrounding the corner. 

A scanning strategy is called: 
\begin{compactitem}
	\item \emph{continuous}, if for any $k = 2, \dots, (m + 2) \cdot (n + 2)$, $v_k(m, n)$ is a contiguous position of $v_{k - 1}(m, n)$ or $v_k(m, n)$ and $v_{k - 1}(m, n)$ are at the border of the image. 
	\item \emph{normalized}, if $v_{(m + 2) \cdot (n + 2)}$ is a corner. 
\end{compactitem}

As an example we can define a scanning strategy, which is scanning the picture row by row from top to bottom:

\begin{example}
\label{example:scanning_strategy}
	\begin{align*}
		\mathfrak{s}_{row}(i, j, m, n) = \left\{\begin{tabular}{lr}
			(i, j + 1) & \text{ if } j $\leq$ n \\
			(i + 1, 1) & \text{ if } j = n + 1 \text{ and }  i $\leq$ m. 
		\end{tabular}\right.
	\end{align*}
\end{example}

This scanning strategy is continuous as well as normalized. 

The scanning strategy $\mathfrak{s}$ is always visiting positions which top-left contiguous positions are already visited. That leads to the definition of corner-2-corner (see $c2c$ in Section~\ref{drec}) directions. 

\begin{definition}
	A scanning strategy $\mathfrak{s}$ is $tl2br$-directed, if for any $(m, n) \in \mathbb{N} \times \mathbb{N}$ and $k = 1, \dots, (m + 2) \cdot (n + 2)$ the top-left-contiguous positions of $v_k(m, n)$ are in $V_{\mathfrak{s}, k}(m, n)$. 
\end{definition}

This definition can be similarly defined for any corner-2-corner direction, where the two corners are diagonal counterparts. We can see that $\mathfrak{s}_{row}$ is a $tl2br$-directed scanning strategy. With these definitions we are able to introduce the tiling automaton. 

\begin{definition}
	A quadruple $\mathcal{A} = (T, \mathfrak{s}, D_0, \delta)$ is called a tiling
	automaton (TA) of type $tl2br$, where:
	
	\begin{compactitem}
		\item $T = (\Sigma, \Gamma, \Theta, \pi)$ is a tiling system,
		\item $\mathfrak{s}$ is a tl2br-directed scanning strategy,
		\item $D_0$ is an initial data structure which supports $\mathtt{state_1}(D)$, $\mathtt{state_2}(D)$, $\mathtt{state_3}(D)$ and $\mathtt{update}(D, \gamma)$ for any data structure $D$ and $\gamma \in \Gamma \cup \{\#\}$ and
		\item $\delta: (\Gamma \cup \{\#\})^3 \times (\Sigma \times \{\#\}) \rightarrow 2^{\Gamma \cup \{\#\}}$ is a partial transition function with 
		
		$\gamma_4 \in \delta(\gamma_1, \gamma_2, \gamma_3, \sigma)$ if 
		\begin{tabular}{|c|c|}
			\hline
			$\gamma_1$ & $\gamma_2$ \\
			\hline
			$\gamma_3$ & $\gamma_4$ \\
			\hline
		\end{tabular} $\in \Theta$
		and $\pi(\gamma_4) = \sigma$ if $\sigma \in \Sigma$, $\gamma_4 = \#$ otherwise. 
	\end{compactitem}
\end{definition}

This definition can be used similarly with any corner-2-corner direction. We speak about tiling automaton (TA), if it is a tiling automaton of any type $d \in c2c$. 

The use of the data structure will be clear after the next example. Until now it is important that the three state-functions are used to determine the state of the automaton whereas the update function is called after each step to feed the data structure with relevant information. 

A configuration of a tiling automaton is a quadruple $(p, i, j, D)$ and contains the picture $p$ of size $(m, n)$, the current position $(i, j)$ and the current data structure $D$. If we derive $(p, i', j', D')$ from $(p, i, j, D)$ in one step, we write: $(p, i, j, D) \vdash (p, i', j', D')$. A derivation can only be achieved if 

\begin{compactitem}
	\item $\mathfrak{s}(i, j, m, n)$ and 
	\item $\delta(\mathtt{state_1}(D), \mathtt{state_2}(D), \mathtt{state_3}(D), p(i, j))$
\end{compactitem} 
are both defined. Furthermore $(i', j') = \mathfrak{s}(i, j, m, n)$ is the next position of the scanning strategy and $D'$ is the data structure after calling $\mathtt{update}(D, \gamma_4)$ with $\gamma_4 \in \\\delta(\gamma_1, \gamma_2, \gamma_3, p(i, j))$. As usual, $\vdash^*$ is the reflexive transitive closure of $\vdash$. 

The automaton accepts a picture if there exists a computation $(p, i_0, j_0, D_0) \vdash^* \\(p, i', j', D')$ where $(i', j')$ is the last position in $V_{\mathfrak{s}, (m + 2) \cdot (n + 2)}(m, n)$. Otherwise the automaton rejects the input picture. 

In words, the automaton is moving over the picture $p$ according to the scanning strategy $\mathfrak{s}$. The picture $p$ itself is never modified. At any position $(i, j)$, the automaton has three states from the data structure and checks, whether there exists a value $\gamma_4$ which can be projected to the character of the current position using the function $\pi$. If there exists at least one possible value for $\gamma_4$, it is checked whether the three states and $\gamma_4$ are forming a valid tile. If there are more than one possible matching values, the selection is non-deterministic. If every position of the picture has been visited, the automaton found a valid tiling of the picture and accepts.  

To underline that these automata accept the same languages as tiling systems, we will construct an automaton which accepts the same language as an arbitrary tiling system. 

\begin{example}
	Let $T = (\Sigma, \Gamma, \Theta, \pi)$ be a tiling system for a language L. We construct a tiling automaton $\mathcal{A}_{row} = (T, \mathfrak{s}_{row}, D_{row_0}, \delta_{row})$, based on $T$ and the scanning strategy $\mathfrak{s}_{row}$ of Example~\ref{example:scanning_strategy}.
	The data structure has the size $m + 3$ and is initially filled with \#'s. The functions $\mathtt{state_1}(D)$, $\mathtt{state_2}(D)$ and $\mathtt{state_3}(D)$ are returning the first, second and last element of the data structure D respectively. The function $\mathtt{update}(D, \gamma)$ for any $\gamma \in \Gamma \cup \{\#\}$ deletes the first element in the data structure and appends $\gamma$. Due to the use of $\mathfrak{s}_{row}$, the data structure is moving row-wise over the picture and is illustrated in the following picture: 
	
	\begin{center}
		\begin{tabular}{|cc|c|c|c|c|cc|}
			\hline
			\# & \multicolumn{6}{c}{\dots}& \# \\
			\vdots & \multicolumn{6}{c}{} & \vdots \\
			\cline{4-8}
			\dots & \multicolumn{2}{c|}{\dots} & $1$ & $2$ & & \multicolumn{1}{c|}{\dots} & \# \\
			\hline
			& \dots & $m + 2$ & $m + 3$ & $p(i, j)$ &\multicolumn{2}{c}{\dots} & \\
			\cline{1-5}
			\vdots & \multicolumn{6}{c}{} & \vdots \\
			\# & \multicolumn{6}{c}{\dots}& \# \\
			\hline
		\end{tabular}
	\end{center}
	
	The automaton is currently at position $(i, j)$ and the functions $\mathtt{state_1}(D)$, $\mathtt{state_2}(D)$ and $\mathtt{state_3}(D)$ are returning the values of the cells numbered with $1$, $2$ and $m + 3$. 
	
	Finally, we have to define the transition function $\delta_{row}$.	$\gamma_4 \in \delta_{row}(\gamma_1, \gamma_2, \gamma_3, p(i, j))$ if 
		\begin{tabular}{|c|c|}
			\hline
			$\gamma_1$ & $\gamma_2$ \\
			\hline
			$\gamma_3$ & $\gamma_4$ \\
			\hline
		\end{tabular} $\in \Theta$
		and $\pi(\gamma_4) = p(i, j)$ if $p(i, j) \in \Sigma$. $\gamma_4 = \#$ otherwise. 
\end{example}

It can be shown that this automaton accepts the same language as the tiling system $T$. Furthermore, the class of languages accepted by tiling automata is the class REC \cite{anselmo2009computational}. 